package editor.cn;

import java.util.Arrays;

/**
 * @Author: Ethan Yankang
 * @Program: 秋招算法真题
 * @Date: 2024-09-14 20:37
 **/
class Solution {
    static int count=0;

    public static void main(String[] args) {
        int[] nums=new int[]{1,2,2,3,1,2,1};
        System.out.println(new Solution().findTargetSumWays(nums,4));
    }
    public int findTargetSumWays(int[] nums,int space) {


        Arrays.sort(nums);
        backTraceing(nums,space,0,0);
        return count;
    }


    //使用回溯法来做
    private void backTraceing(int[] nums, int space, int startIndex, int sum) {
        if (sum==space){
            count++;
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (sum+nums[i]>space)break;
            sum+=nums[i];
            backTraceing(nums,space,i+1,sum);
            sum-=nums[i];
        }
    }
}
